#include "evaluate.h"

extern int gridUnit;
extern int x_gridNum;
extern int y_gridNum;
extern int numBins;
extern ckt this_ckt;
extern double HPWL, penalty, displacement, max_displacement, targUt;
extern string directory;
extern vector<double> util_array;


/*----------------------------------------------------------------------*/
/*  Desc:   A function to measure single cell displacement (L-1 norm)   */
/*----------------------------------------------------------------------*/

int cell_displacement(int target_x, int target_y, node & this_node)
{
	return abs(target_x - this_node.initial_x) + abs(target_y - this_node.initial_y);
}

/*-----------------------------------------------*/
/*  Desc:   A function to measure displacement   */
/*-----------------------------------------------*/
double measure_displacement(ckt & ptrckt, const char * input)
{
	ifstream inpl(input);
	if(!inpl.good())
	{
		cout << input << " does not exist. exiting .. "<<endl;
		exit(1);
	}

	double maxdisp=0.0;

	//Skip irrelevent information
	string tmpStr;
	do {
		inpl >> tmpStr;
	} while(ptrckt.name2id.find(tmpStr) == ptrckt.name2id.end()); 

	bool isMovable = true;
	for(unsigned i = 0; i < ptrckt.nodes.size(); i++)
	{
		if(!isMovable)
			inpl >> tmpStr;

		map<string, unsigned>::iterator it = ptrckt.name2id.find(tmpStr);
		if(it == ptrckt.name2id.end())
		{
			cout << "can't find a node " << tmpStr << ". existing .." <<endl;
			exit(1);
		}

		double x_coord, y_coord;
		inpl >> x_coord >> y_coord >> tmpStr >> tmpStr;
		/* measure maximum L1 displacement */
		double disp = fabs(x_coord - ptrckt.nodes[it->second].x_coord) + fabs(y_coord - ptrckt.nodes[it->second].y_coord);
		maxdisp = max(maxdisp, disp);
		if(disp > max_displacement)
			cout << disp << endl; 

		inpl >> tmpStr;
		if(tmpStr=="/FIXED" || tmpStr=="/FIXED_NI")
			isMovable=false;
		else
			isMovable=true;
	}
	inpl.close();
	return maxdisp;
}

/*--------------------------------------*/
/*  Desc:   A function to measure ABU   */
/*--------------------------------------*/
double measure_ABU(ckt &ptrckt, double unit, double targUt)
{
	cout << "  numBins           : "<< numBins << " ( "<< x_gridNum << " x "<< y_gridNum << " )"<< endl;
	cout << "  bin dimension     : "<< gridUnit << " x " << gridUnit << endl;

	/* 0. initialize density map */
	vector<density_bin> bins(numBins);
	for(int j = 0; j < y_gridNum; j++)
		for(int k = 0; k < x_gridNum; k++)
		{
			unsigned binId = j * x_gridNum + k;

			bins[binId].lx = ptrckt.lx + k * gridUnit;
			bins[binId].ly = ptrckt.by + j * gridUnit;
			//bins[binId].hx = bins[binId].lx + gridUnit;
			//bins[binId].hy = bins[binId].ly + gridUnit;
			bins[binId].hx = min(bins[binId].lx + gridUnit, ptrckt.rx);
			bins[binId].hy = min(bins[binId].ly + gridUnit, ptrckt.ty);

			bins[binId].area = max((bins[binId].hx - bins[binId].lx) * (bins[binId].hy - bins[binId].ly), 0);
			bins[binId].m_util = 0.0;
			bins[binId].f_util = 0.0;
			bins[binId].free_space = bins[binId].area;
		}

	/* 1. build density map */
	/* (a) fixed/movable objects */
	for(unsigned i = 0; i < ptrckt.nodes.size(); i++)
	{
		if(ptrckt.nodes[i].isNI || ptrckt.nodes[i].shapeIds.size() != 0)
			continue;

		int lcol = max((int)floor((double)(ptrckt.nodes[i].x_coord - ptrckt.lx)/gridUnit), 0);
		int rcol = min((int)floor((double)(ptrckt.nodes[i].x_coord + ptrckt.nodes[i].width - ptrckt.lx)/gridUnit), x_gridNum - 1);
		int brow = max((int)floor((double)(ptrckt.nodes[i].y_coord - ptrckt.by)/gridUnit), 0);
		int trow = min((int)floor((double)(ptrckt.nodes[i].y_coord + ptrckt.nodes[i].height - ptrckt.by)/gridUnit), y_gridNum - 1);
		// The left edge of a node resides in the (lcol)_th bin in a row...	

		// For all the overlapped bins of a node
		for(int j = brow; j <= trow; j++)
			for(int k = lcol; k <= rcol; k++)
			{
				unsigned binId= j * x_gridNum+k;

				/* get intersection */
				double lx = max(bins[binId].lx, ptrckt.nodes[i].x_coord);
				double hx = min(bins[binId].hx, ptrckt.nodes[i].x_coord + ptrckt.nodes[i].width);
				double ly = max(bins[binId].ly, ptrckt.nodes[i].y_coord);
				double hy = min(bins[binId].hy, ptrckt.nodes[i].y_coord + ptrckt.nodes[i].height);

				if((hx-lx) > 1.0e-5 && (hy-ly) > 1.0e-5)
				{
					double common_area = (hx-lx) * (hy-ly);
					if(ptrckt.nodes[i].isFixed)
						bins[binId].f_util += common_area;
					else 
						bins[binId].m_util += common_area;
				}
			}
	}

	/* (b) non-rectangular fixed shapes */
	for(unsigned i = 0; i < ptrckt.nodes.size(); i++)
		for(unsigned m = 0; m < ptrckt.nodes[i].shapeIds.size(); m++) // Skip normal nodes because m = 0
		{    
			// Divide non-regular fixed shapes into rectangles and use tha above method to calculate areas
			unsigned s = ptrckt.nodes[i].shapeIds[m];
			int lcol = max((int)floor((double)(ptrckt.shapes[s].x_coord - ptrckt.lx)/gridUnit), 0);
			int rcol = min((int)floor((double)(ptrckt.shapes[s].x_coord + ptrckt.shapes[s].width - ptrckt.lx)/gridUnit), x_gridNum-1);
			int brow = max((int)floor((double)(ptrckt.shapes[s].y_coord - ptrckt.by)/gridUnit), 0);
			int trow = min((int)floor((double)(ptrckt.shapes[s].y_coord + ptrckt.shapes[s].height - ptrckt.by)/gridUnit), y_gridNum-1);

			for(int j=brow;j<=trow;j++)
				for(int k=lcol;k<=rcol;k++)
				{
					unsigned binId= j*x_gridNum+k;

					/* get intersection */
					double lx = max(bins[binId].lx, ptrckt.shapes[s].x_coord);
					double hx = min(bins[binId].hx, ptrckt.shapes[s].x_coord + ptrckt.shapes[s].width);
					double ly = max(bins[binId].ly, ptrckt.shapes[s].y_coord);
					double hy = min(bins[binId].hy, ptrckt.shapes[s].y_coord + ptrckt.shapes[s].height);

					if((hx-lx) > 1.0e-5 && (hy-ly) > 1.0e-5)
					{
						double common_area = (hx - lx) * (hy - ly);
						bins[binId].f_util += common_area;
					}
				}
			}

	/* (c) row blockages */
	for(unsigned i = 0; i < ptrckt.blks.size(); i++)
	{
		int lcol = max((int)floor((double)(ptrckt.blks[i].x_coord - ptrckt.lx)/gridUnit), 0);
		int rcol = min((int)floor((double)(ptrckt.blks[i].x_coord + ptrckt.blks[i].width - ptrckt.lx)/gridUnit), x_gridNum-1);
		int brow = max((int)floor((double)(ptrckt.blks[i].y_coord - ptrckt.by)/gridUnit), 0);
		int trow = min((int)floor((double)(ptrckt.blks[i].y_coord + ptrckt.blks[i].height - ptrckt.by)/gridUnit), y_gridNum-1);

		for(int j = brow; j <= trow; j++)
			for(int k = lcol; k <= rcol; k++)
			{
				unsigned binId = j * x_gridNum + k;

				/* get intersection */
				double lx = max(bins[binId].lx, ptrckt.blks[i].x_coord);
				double hx = min(bins[binId].hx, ptrckt.blks[i].x_coord+ptrckt.blks[i].width);
				double ly = max(bins[binId].ly, ptrckt.blks[i].y_coord);
				double hy = min(bins[binId].hy, ptrckt.blks[i].y_coord+ptrckt.blks[i].height);

				if((hx-lx) > 1.0e-5 && (hy-ly) > 1.0e-5)
				{
					double common_area = (hx-lx) * (hy-ly);
					bins[binId].f_util += common_area;
				}
			}
	}

	vector<double> util_array(numBins, 0.0);
	/* 2. determine the free space & utilization per bin */
	for(int j = 0; j < y_gridNum; j++)
	{	
		for(int k = 0; k < x_gridNum; k++)
		{
			unsigned binId = j * x_gridNum + k;
			if(bins[binId].area > gridUnit * gridUnit * BIN_AREA_THRESHOLD)
			{
				bins[binId].free_space = bins[binId].area - bins[binId].f_util;
				if(bins[binId].free_space > FREE_SPACE_THRESHOLD * bins[binId].area)
					util_array[binId] = bins[binId].m_util / bins[binId].free_space;
			}
			
		}
	}

	bins.clear();
	sort(util_array.begin(), util_array.end());

	/* 3. obtain ABU numbers */
	double abu1=0.0, abu2=0.0, abu5=0.0, abu10=0.0, abu20=0.0;
	int clip_index = 0.01*numBins;
	for(int j=numBins-1;j>numBins-1-clip_index;j--) {
		abu1+=util_array[j];
	}
	abu1=(clip_index) ? abu1/clip_index : util_array[numBins-1];

	clip_index = 0.02*numBins;
	for(int j=numBins-1;j>numBins-1-clip_index;j--) {
		abu2+=util_array[j];
	}
	abu2=(clip_index) ? abu2/clip_index : util_array[numBins-1];

	clip_index = 0.05*numBins;
	for(int j=numBins-1;j>numBins-1-clip_index;j--) {
		abu5+=util_array[j];
	}
	abu5=(clip_index) ? abu5/clip_index : util_array[numBins-1];

	clip_index = 0.10*numBins;
	for(int j=numBins-1;j>numBins-1-clip_index;j--) {
		abu10+=util_array[j];
	}
	abu10=(clip_index) ? abu10/clip_index : util_array[numBins-1];
	
	clip_index = 0.20*numBins;
	for(int j=numBins-1;j>numBins-1-clip_index;j--) {
		abu20+=util_array[j];
	}
	abu20=(clip_index) ? abu20/clip_index : util_array[numBins-1];
	util_array.clear();

	cout << "  target util       : "<<targUt <<endl;
	cout << "  ABU_2,5,10,20     : "<< abu2 <<", "<< abu5 <<", "<< abu10 <<", "<< abu20 <<endl;

	/* calculate overflow */
	abu1=max(0.0, abu1/targUt-1.0);
	abu2=max(0.0, abu2/targUt-1.0);
	abu5=max(0.0, abu5/targUt-1.0);
	abu10=max(0.0, abu10/targUt-1.0);
	abu20=max(0.0, abu20/targUt-1.0);
	return (ABU2_WGT*abu2+ABU5_WGT*abu5+ABU10_WGT*abu10+ABU20_WGT*abu20)/(double)(ABU2_WGT+ABU5_WGT+ABU10_WGT+ABU20_WGT);
}


/*--------------------------------------*/
/*  Desc:   A function to measure HPWL  */
/*--------------------------------------*/
double measure_HPWL(ckt &ptrckt)
{
	double totalX=0.0;
	double totalY=0.0;

	for(unsigned i = 0; i < ptrckt.nets.size(); i++)
	{
		double netMaxX=ptrckt.lx, netMinX=ptrckt.rx;
		double netMaxY=ptrckt.by, netMinY=ptrckt.ty;

		for(unsigned j = 0;j < ptrckt.nets[i].nodeIds.size(); j++)
		{
			double x_pinloc = ptrckt.nodes[ ptrckt.nets[i].nodeIds[j] ].x_coord + 0.5*ptrckt.nodes[ ptrckt.nets[i].nodeIds[j] ].width+ptrckt.nets[i].x_offset[j];
			double y_pinloc = ptrckt.nodes[ ptrckt.nets[i].nodeIds[j] ].y_coord + 0.5*ptrckt.nodes[ ptrckt.nets[i].nodeIds[j] ].height+ptrckt.nets[i].y_offset[j];
			if(j==0)
			{
				netMaxX = netMinX=x_pinloc;
				netMaxY = netMinY=y_pinloc;
			}
			else
			{
				netMaxX = max(netMaxX, x_pinloc);
				netMinX = min(netMinX, x_pinloc);
				netMaxY = max(netMaxY, y_pinloc);
				netMinY = min(netMinY, y_pinloc);
			}
		}
		totalX += netMaxX-netMinX;
		totalY += netMaxY-netMinY;
	}
	cout << "  HPWL              : " << totalX+totalY << " ( " <<totalX << ", "<< totalY << " ) "<<endl;
	return totalX + totalY;
}

double calculate_local_HPWL(ckt & ptrckt, set<int> & related_nets)
{
	set<int>::iterator it;
	int local_HPWL = 0;
	for(it = related_nets.begin(); it != related_nets.end(); it++)
	{
		net & this_net = ptrckt.nets[*it];
		local_HPWL += single_net_HPWL(ptrckt, this_net);
	}
	return local_HPWL;
}

double single_net_HPWL(ckt & ptrckt, net & this_net)
{
	double netMaxX = ptrckt.lx;
	double netMinX = ptrckt.rx;
	double netMaxY = ptrckt.by;
	double netMinY = ptrckt.ty;

	for(unsigned j = 0;j < this_net.nodeIds.size(); j++)
	{
		double x_pinloc = ptrckt.nodes[ this_net.nodeIds[j] ].x_coord 
					+ 0.5*ptrckt.nodes[ this_net.nodeIds[j] ].width + this_net.x_offset[j];
		double y_pinloc = ptrckt.nodes[ this_net.nodeIds[j] ].y_coord 
					+ 0.5*ptrckt.nodes[ this_net.nodeIds[j] ].height + this_net.y_offset[j];
		if(j == 0)
		{
			netMaxX = netMinX = x_pinloc;
			netMaxY = netMinY = y_pinloc;
		}
		else
		{
			netMaxX = max(netMaxX, x_pinloc);
			netMinX = min(netMinX, x_pinloc);
			netMaxY = max(netMaxY, y_pinloc);
			netMinY = min(netMinY, y_pinloc);
		}
	}
	return (netMaxX - netMinX + netMaxY - netMinY);
}

int delta_HPWL(ckt & ptrckt, int NodeID, int x_displacement, int y_displacement)
{
	if(x_displacement == 0 && y_displacement == 0)
		return 0;

	double d_HPWL = 0;
	node * this_node = & ptrckt.nodes[NodeID];

	for(int i = 0; i < this_node->pins.size(); i++)
	{
		int netID = this_node->pins[i].pin2net;
		net * this_net = & ptrckt.nets[netID];

		double original_dx = this_net->max_X - this_net->min_X;
		double original_dy = this_net->max_Y - this_net->min_Y;

		double netMaxX = ptrckt.lx;
		double netMinX = ptrckt.rx;
		double netMaxY = ptrckt.by;
		double netMinY = ptrckt.ty;

		for(unsigned j = 0; j < this_net->nodeIds.size(); j++)
		{
			node * cur_node = & ptrckt.nodes[ ptrckt.nets[netID].nodeIds[j] ];

			double x_pinloc = cur_node->x_coord + 0.5 * cur_node->width + this_net->x_offset[j];
			double y_pinloc = cur_node->y_coord + 0.5 * cur_node->height + this_net->y_offset[j];

			if(this_net->nodeIds[j] == NodeID)
			{
				x_pinloc += x_displacement;
				y_pinloc += y_displacement;
			}
				
			if(j == 0)
			{
				netMaxX = netMinX = x_pinloc;
				netMaxY = netMinY = y_pinloc;
			}
			else
			{
				netMaxX = max(netMaxX, x_pinloc);
				netMinX = min(netMinX, x_pinloc);
				netMaxY = max(netMaxY, y_pinloc);
				netMinY = min(netMinY, y_pinloc);
			}
		}
		d_HPWL += (netMaxX - netMinX + netMaxY - netMinY) - (original_dx + original_dy);
 	}
 	return d_HPWL;	
}

int delta_HPWL_abs(ckt & ptrckt, node & this_node, int dest_x, int dest_y)
{
	set<int> related_nets;
	vector<pin>::iterator it;
	for(it = this_node.pins.begin(); it != this_node.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	int src_x = this_node.x_coord;
	int src_y = this_node.y_coord;
	int src_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	this_node.x_coord = dest_x;
	this_node.y_coord = dest_y;
	int dest_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	this_node.x_coord = src_x;
	this_node.y_coord = src_y;
	return (dest_HPWL - src_HPWL);
}

int tinyrow_distance(tinyRow & src_row, tinyRow & dest_row)
{
	int src_row_x = (src_row.lx + src_row.rx) / 2;
	int dest_row_x = (dest_row.lx + dest_row.rx) / 2;
	return abs(src_row_x - dest_row_x) + abs(src_row.y - dest_row.y);
}

void tinyRow_statistics(ckt & ptrckt)
{
	// Statistics
	int N_invalid = 0;
	int N0 = 0;
	int N1 = 0;
	int N2 = 0; 
	int N3 = 0;
	int N4 = 0;
	int N5 = 0;
	int N6plus = 0;

	for(int i = 0; i < 9 * numBins; i++)
	{
		tinyRow & this_row = ptrckt.tinyRows[i];
		if(!this_row.isValid)
			N_invalid++;
		else
		{
			switch(this_row.NodeID.size())
			{
				case 0:
					N0++;
					break;
				case 1:
					N1++;
					break;
				case 2:
					N2++;
					break;
				case 3:
					N3++;
					break;
				case 4:
					N4++;
					break;
				case 5:
					N5++;
					break;
				default:
					N6plus++;
			}
		}
	}
	cout << "-------------------TinyRow Statistics-----------------------" << endl;
	cout << "0: " << N0 << "; 1: " << N1 << "; 2: "<< N2 << "; 3: " << N3 <<
			 "; 4: " << N4 << "; 5: " << N5 << "; 6+: " << N6plus << endl;
	cout << "Invalid tinyRows: " << N_invalid << endl;
	cout << "------------------------------------------------------------" << endl;
}

int opt_center(ckt & ptrckt, node & this_node)
{
	vector<double> lx;
	vector<double> rx;

	//traverse all the nets of this node
	for(int i = 0; i < this_node.pins.size(); i++)
	{
		int netID = this_node.pins[i].pin2net;
		net & this_net = ptrckt.nets[netID];
		double x_pinloc = this_node.x_coord + 0.5 * this_node.width + this_node.pins[i].x_offset;
		
		if( (x_pinloc <= this_net.max_X) && (x_pinloc >= this_net.min_X) )
		{	// The node is within the original bounding box
			lx.push_back(this_net.min_X);
			rx.push_back(this_net.max_X);
		}
		else // Recalculate the bounding box
		{
			double netMaxX = ptrckt.lx;
			double netMinX = ptrckt.rx;
			for(unsigned j = 0; j < this_net.nodeIds.size(); j++)
			{
				node & cur_node = ptrckt.nodes[ ptrckt.nets[netID].nodeIds[j] ];
				double x_pinloc = cur_node.x_coord + 0.5 * cur_node.width + this_net.x_offset[j];

				if(this_net.nodeIds[j] == this_node.ID)
					continue; // Skip this node 
					
				if(j == 0)
				{
					netMaxX = netMinX = x_pinloc;
				}
				else
				{
					netMaxX = max(netMaxX, x_pinloc);
					netMinX = min(netMinX, x_pinloc);
				}
			}

			lx.push_back(netMinX);
			rx.push_back(netMaxX);
		}

	}
	// Calculate the median, thus deriving the optimal region of current node
	
	int num_net = this_node.pins.size();
	double opt_lx, opt_rx;
	sort(lx.begin(), lx.end());
	sort(rx.begin(), rx.end());


	if(num_net % 2 == 0)
	{
		if(num_net != 0)
		{
			opt_lx = ( lx[num_net / 2 - 1] + lx[num_net / 2] ) / 2;
			opt_rx = ( rx[num_net / 2 - 1] + rx[num_net / 2] ) / 2;
		}		
		else
		{
			opt_lx = opt_rx = this_node.x_coord;
		}
	}
	else
	{
		opt_lx = lx[(num_net - 1) / 2];
		opt_rx = rx[(num_net - 1) / 2];
	}
	return (opt_lx + opt_rx) / 2;
}